package com.longge;

import java.util.HashMap;
import java.util.Map;

/**
 * @创建人 xinglongge
 * @创建时间 2021/11/19
 * @描述
 */
public class IntegerReplacement {

    /**
     * 给定一个正整数 n ，你可以做如下操作：
     * <p>
     * 如果 n 是偶数，则用 n / 2替换 n 。
     * 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
     * n 变为 1 所需的最小替换次数是多少？
     *
     * @param n
     * @return
     */
    private Map<Integer, Integer> map = new HashMap<>();

    public int integerReplacement(int n) {
        if (n == 1) return 0;
        if (!map.containsKey(n)) {
            if (n % 2 == 0) {
                map.put(n, 1 + integerReplacement(n / 2));
            } else {
                map.put(n, 2 + Math.min(integerReplacement(n / 2), integerReplacement(n / 2 + 1)));
            }
        }
        return map.get(n);
    }

}
